package problem279_Perfect_Squares;

import java.util.Arrays;

/**
 * dp[i]表示数字i的最小完美平方数
 * http://blog.csdn.net/happyaaaaaaaaaaa/article/details/51584790
 */
public class Solution {
	 public int numSquares(int n) {
	     int[] dp=new int[n+1];
	     Arrays.fill(dp, Integer.MAX_VALUE);
	     for(int i=1;i*i<=n;i++){
	    	 dp[i*i]=1;
	     }
	     if(dp[n]!=Integer.MAX_VALUE)
	    	 return dp[n];
	     for(int i=1;i<=n;i++){
	    	 for(int j=1;i+j*j<=n;j++){
	    		 dp[i+j*j]=Math.min(dp[i+j*j], dp[i]+1);
	    	 }
	     }
	     return dp[n];
	 }
}
